【JS每日一算法】19.两两交换链表中的节点(迭代法、递归回溯法) |
您所在的位置：网站首页 › 前端 算法 › 【JS每日一算法】19.两两交换链表中的节点(迭代法、递归回溯法) |
【JS每日一算法】19.两两交换链表中的节点(迭代法、递归回溯法)
|
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 示例： 更多JS版本题解点击链接关注该仓库👀 /** * @description: 递归回溯方法 TC:O(n) SC:O(n) * @author: JunLiangWang * @param {*} node * @return {*} */ function recursionBacktracking(node) { /** * 该方案利用递归回溯的方式，递归判断当前节点以及其后一个节点是否存在， * 如果不存在，证明已无节点可交换，则直接返回当前节点；否则，则将当前 * 节点与其下一个节点进行交换。交换过程为：先将当前节点的下一个节点取 * 出并保存(nextNode)，然后将当前节点的下一个节点更新为nextNode后续 * 节点继续递归的结果，然后将nextNode的下一个节点更新为当前节点，此时 * nextNode则变更为当前节点的前一个节点，返回nextNode即可。 */ // 判断当前节点与其下一个节点是否存在，如果存在则将两节点位置交换 if(node&&node.next) { // 先保存当前节点的下一个节点(nextNode) let nextNode=node.next; // 将当前节点的下一个节点更新为nextNode后续节点继续递归的结果 node.next=recursionBacktracking(nextNode.next); // 将nextNode的下一个节点更新为当前节点 nextNode.next=node; // 此时nextNode已为当前节点的前一个节点，返回nextNode即可 return nextNode; } // 不存在证明已无可交换节点，直接返回即可当前节点即可 else { return node; } } /** * @description: 迭代法 TC:O(n) SC:O(n) * @author: JunLiangWang * @param {*} head * @return {*} */ function iteration(head){ /** * 该方案利用迭代，每次遍历链表的两个节点，将其交换，直至遍历结束 */ // 如果当前节点为空或其后一个节点为空，证明无需要交换的节点，直接返回当前节点即可 if(!head||!head.next)return head; // 新的头节点为原链表的第二个节点 const NEW_HEAD=head.next; // 上一个节点初值为空 let lastNode=null; // 当前节点初值为原链表第一个节点 let currentNode=head; // 当前节点不为空且其下一个节点也不为空，证明仍存在需要交换的节点 while(currentNode&¤tNode.next) { // 将当前节点的下一个节点取出保存(nextNode) let nextNode=currentNode.next; // 将当前节点的下一个节点更新为nextNode的下一个节点 currentNode.next=nextNode.next; // nextNode的下一个节点更新为当前节点，此时位置已完成交换 nextNode.next=currentNode; // 如果存在上一个节点，则需要将上一个节点的下一个节点更新为 // 已经交换位置的nextNode if(lastNode)lastNode.next=nextNode; // 上一个节点更新为当前节点 lastNode=currentNode; // 当前节点更新为其下一个节点 currentNode=currentNode.next; } // 返回新链表 return NEW_HEAD; } 复制代码 |
【本文地址】